\documentclass[utf8]{beamer}
\usepackage{import}
\usepackage{graphicx}
\usepackage[french]{babel}
\graphicspath{{img/}}

\usetheme{Darmstadt}

\title{Projet AMR}
\subtitle{Coloration de graphes}
\date{Janvier 2011}

\author{
Mohamed El-Fardi
\and
Lo\"ic Fournier
\and
Yann Hauquin
}
\institute{Universit\'e de Bordeaux I}
\setbeamercovered{transparent}
\begin{document}

\frame{\titlepage}

% ---------------------------

\begin{frame}
\frametitle{Quel est le but du projet ?}
\begin{itemize}
\item \uncover<1->{Implémenter des algorithmes de graphes k-coloriables}
\item \uncover<2->{Implémenter des algorithmes (heuristiques) de
      coloration de graphes}
\item \uncover<3->{Effectuer des tests d'efficacité}
\item \uncover<4->{Poser une conclusion}
\end{itemize}
\end{frame}

% ---------------------------

\begin{frame}
\frametitle{Architecture}

\begin{itemize}
\item \uncover<1->{Projet écrit en C++}
\begin{itemize}
\item \uncover<2->{Architecture modulaire et ré-utilisable}
\end{itemize}
\item \uncover<3->{Utilisation de listes d'adjacences comme structure de
      données}
\end{itemize}
\end{frame}


% ---------------------------

\begin{frame}
\frametitle{Architecture}
Utilisation de la mémoire
\begin{center}
Image liste | Image matrice
\end{center}
\end{frame}


% ---------------------------

\begin{frame}
\frametitle{Algorithmes}
\begin{block}{Algorithme Glouton}
\begin{itemize}
\item \uncover<2->{Naïf}
\item \uncover<3->{Itératif}
\item \uncover<4->{Pas efficace}
\item \uncover<5->{Rapide}
\end{itemize}
\end{block}
\end{frame}

% ---------------------------

% ---------------------------

\begin{frame}
\frametitle{Algorithmes}
\begin{block}{Algorithme Backtrack}
\begin{itemize}
\item \uncover<2->{Récursif}
\item \uncover<3->{Relativement efficace}
\item \uncover<4->{Lent}
\end{itemize}
\end{block}
\end{frame}

% ---------------------------


% ---------------------------

\begin{frame}
\frametitle{Algorithmes}
\begin{block}{Algorithme No-Choice}
\begin{itemize}
\item \uncover<2->{Itératif}
\item \uncover<3->{Assez efficace}
\item \uncover<4->{Relativement rapide}
\end{itemize}
\end{block}
\end{frame}

% ---------------------------

\begin{frame}
\frametitle{Algorithmes}
\begin{block}{Réduction au problème SAT}

On exprime sous forme de formule logique la propriété d'un graphe d'être
k-coloriable.
~\\~\\
\`A tous les sommets i $\in$ V, on associe k variables : \\
$c_{i}^{k}\left\{\begin{tabular}{l}
- 1 si le sommet i est de couleur $c^{k}$ \\
- 0 sinon
\end{tabular}\right .$
~\\~\\
Chaque sommet a au moins une couleur :\\
$\Phi_{1} = \bigwedge_{i \in V}{(c_{i}^{1} \lor c_{i}^{2} \lor \dots
  \lor c_{i}^{k})}$
~\\~\\
Chaque sommet comporte au plus une couleur:\\
$\Phi_{2} = \bigwedge_{i \in V}{\left[(\lnot c_{i}^{1} \lor \lnot
    c_{i}^2 \lor \dots \lor \lnot c_{i}^{k-1})$$\land(\lnot c_{i}^{1} \lor
    \lnot c_{i}^{2} \lor \dots \lor \lnot c_{i}^{k-2} \lor \lnot
    c_{i}^{k})$$\land \dots \land(\lnot c_{i}^{2} \lor \lnot c_{i}^{3} \lor
    \dots \lor \lnot c_{i}^{k})\right]}$
~\\~\\
Deux voisins ne comportent pas la même couleur :\\
$\Phi_{3} = \bigwedge_{(i,j) \in E}{\left[\lnot (c_{i}^{1} \land c_{j}^{1})
    \land \lnot (c_{i}^{2} \land c_{j}^{2}) \land \dots \land
    \lnot (c_{i}^{k} \land c_{j}^{k})\right]}$
~\\~\\
Propriété d'un graphe k-coloriable :\\
$\Phi = \Phi_{1} \land \Phi_{2} \land \Phi_{3}$
~\\~\\

En pratique...
~\\~\\
A partir des clauses ci-dessus, d'un graphe vierge et d'un nombre de couleurs, on génère 
un fichier CNF qui va être analysé par $minisat$ pour savoir si le problème est 
satisfaisable (c'est à dire résolvable) ou pas. Chaque nombre du fichier CNF correspond à une 
variable, le signe négatif correspond à la négation de la variable (par exemple, -12 correspond
à $\lnot c_{i}^{12}$). Si le problème est satisfaisable, $minisat$ nous renvoie en sortie
un fichier comprenant les valeurs booléennes des variables définies. On en déduit, pour
chaque sommet $i$, une unique couleur qui correspond à sa variable de valeur positive $c_{i}^{l}$
($l \in \{1, \dots, k\}$).

\end{block}
\end{frame}

% ---------------------------

\begin{frame}
\frametitle{Complexité des algorithmes}
\centering
blabla sur les complexité
\end{frame}


% ---------------------------

\begin{frame}
\frametitle{Tests d'efficacité}
\begin{block}{Environnement de tests}
\begin{itemize}
\item \uncover<2->{Graphes de taille allant de 1 à 100}
\item \uncover<3->{Probabilité de 0.15}
\item \uncover<4->{Coloriabilité k allant de 2 à 7}
\end{itemize}
\end{block}
\end{frame}

% ---------------------------

\begin{frame}
\frametitle{Test de Glouton}
\includegraphics[scale=0.32]{glouton.png}
\end{frame}

\begin{frame}
\frametitle{Test de Backtrack}
\includegraphics[scale=0.32]{backtrack.png}
\end{frame}

\begin{frame}
\frametitle{Test de No-choice}
\includegraphics[scale=0.32]{nochoice.png}
\end{frame}

\begin{frame}
\frametitle{Test de No-choice optimisé}
\includegraphics[scale=0.32]{nochoice2.png}
\end{frame}

\end{document}
